package com.lw.leetcode.arr.c;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * c
 * arr
 * 2508. 添加边使所有节点度数都为偶数
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/28 10:16
 */
public class IsPossible {

    public boolean isPossible(int n, List<List<Integer>> edges) {
        List<Integer>[] arr = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }
        for (List<Integer> edge : edges) {
            arr[edge.get(0)].add(edge.get(1));
            arr[edge.get(1)].add(edge.get(0));
        }
        int[] items = new int[4];
        int index = 0;
        for (int i = 1; i <= n; i++) {
            if ((arr[i].size() & 1) == 1) {
                if (index == 4) {
                    return false;
                }
                items[index++] = i;
            }
        }
        if (index == 0) {
            return true;
        }
        if (index == 1 || index == 3) {
            return false;
        }
        if (index == 2) {
            if (!arr[items[0]].contains(items[1])) {
                return true;
            }
            for (int i = 1; i <= n; i++) {
                if (i == items[0] || i == items[1]) {
                    continue;
                }
                List<Integer> list = arr[i];
                if (!list.contains(items[0]) && !list.contains(items[1])) {
                    return true;
                }
            }
            return false;
        }
        boolean flag = arr[items[0]].contains(items[1]);
        if (!flag && !arr[items[2]].contains(items[3])) {
            return true;
        }
        flag = arr[items[0]].contains(items[2]);
        if (!flag && !arr[items[1]].contains(items[3])) {
            return true;
        }
        flag = arr[items[0]].contains(items[3]);
        return !flag && !arr[items[1]].contains(items[2]);
    }

}
